package other;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;



/**
 * 力扣 432. 全 O(1) 的数据结构
 * 请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。
 *
 * 实现 AllOne 类：
 *
 * AllOne() 初始化数据结构的对象。
 * inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。
 * dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例保证：在减少计数前，key 存在于数据结构中。
 * getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。
 * getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。
 *
 * 简单来说，统计出现次数，每次会存或者删，要求查询出现最少或最多，查询时间为O(1)
 *
 * */
public class AllOne {
    //root存放空的，最大的再root前面（环形链表，也是链表最后面），最小的都会存放再root后面
    Node root;
    HashMap<String, Node> nodes;
    public AllOne() {
        root = new Node();
        root.next = root;
        root.prev = root;
        nodes = new HashMap<>();
    }

    public void inc(String key) {
        if(nodes.containsKey(key)) {
            Node now = nodes.get(key);
            Node next = now.next;
            //一开始自己指向自己，如果next是自己就说明只有一个数据，如果大于一个数据，则比较后面那个是否大于前者加一，
            //大于的话，直接再默认链表的now结点后面插入新的count+1的结点，并且重新将新的数据放回之前的map里
            if(next == root || next.count > now.count + 1) {
                nodes.put(key,now.insert(new Node(key,now.count + 1)));
            }else {
                //这种情况就是，count + 1后等于之前有的count，直接再那个结点放进node的集合里
                next.keys.add(key);
                //map跟新最新数据
                nodes.put(key,next);
            }
            //由于数据已经处理过，要把老数据删除
            now.keys.remove(key);
            //如果删除后node里的集合空了，那么把链表里这个结点直接删除
            if(now.keys.isEmpty()) {
                now.remove();
            }
        }else {
            //首次插入，或者后面的结点count大于1，就把最新的数据插到root后面，并进行跟新map
            if(root.next == root || root.next.count > 1) {
                nodes.put(key,root.insert(new Node(key,1)));
            }else {
                //之前已经有数据并且都直插入过一次，放入同一个链表结点，并跟新map
                root.next.keys.add(key);
                nodes.put(key,root.next);
            }
        }
    }

    public void dec(String key) {
        Node now = nodes.get(key);
        //若count为1直接删除
        if(now.count == 1) {
            nodes.remove(key);
        }else {
            Node prev = now.prev;
            //如果当前结点上一个是root或者上一个结点小于当前结点count - 1
            //就直接将新的数据插入上一个结点后面，并跟新map
            if(prev == root || prev.count < now.count - 1) {
                nodes.put(key,prev.insert(new Node(key,now.count - 1)));
            }else {
                //这种情况为删除数据后，链表上一个结点的count等于当前结点count - 1
                //直接存入上一个结点，并跟新map
                prev.keys.add(key);
                nodes.put(key,prev);
            }
        }
        //由于数据已经处理过，要把老数据删除
        now.keys.remove(key);
        if(now.keys.isEmpty()) {
            now.remove();
        }
    }

    //取得链表root前面一个结点集合里第一个数据
    public String getMaxKey() {
        return root.prev != root ? root.prev.keys.iterator().next() : "";
    }

    //取得链表root后面一个结点集合里第一个数据
    public String getMinKey() {
        return root.next != root ? root.next.keys.iterator().next() : "";
    }
}

class Node {
    Node prev;
    Node next;
    Set<String> keys;
    int count;

    public Node() {
        this("",0);
    }
    public Node(String key,int count) {
        this.count = count;
        keys = new HashSet<>();
        keys.add(key);
    }

    //插入当前结点后一个结点
    public Node insert(Node node) {
        node.prev = this;
        node.next = this.next;
        node.prev.next = node;
        node.next.prev = node;
        return node;
    }
    //移除当前结点
    public void remove() {
        this.prev.next = this.next;
        this.next.prev = this.prev;
    }
}
